package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 305.岛屿数量     II https://leetcode.com/problems/number-of-islands-ii/
 */
public class LeetCode305 {

    public static List<Integer> numIslands21(int m, int n, int[][] positions) {
        FindUnion findUnion = new FindUnion(m, n);
        List<Integer> ans = new ArrayList<>();
        for (int[] position : positions) {
            ans.add(findUnion.addLands(position[0], position[1]));
        }
        return ans;
    }

    static class FindUnion {
        public int m;
        public int n;
        public int[] parent;
        public int[] size;
        public int[] help;
        public int sets;

        public FindUnion(int m, int n) {
            this.m = m;
            this.n = n;
            parent = new int[m * n];
            size = new int[m * n];
            help = new int[m * n];
            sets = 0;
        }

        public int getIndex(int row, int col) {
            return row * n + col;
        }

        public int find(int cur) {
            int index = 0;
            while (cur != parent[cur]) {
                help[index++] = cur;
                cur = parent[cur];
            }
            for (index--; index >= 0; index--) {
                parent[index] = cur;
            }
            return cur;
        }

        public void union(int r1, int c1, int r2, int c2) {
            if(r1 < 0 || c1 < 0 || r1 >= m || c1 >= n || r2 < 0 || c2 < 0 || r2 >= m || c2 >= n) {
                return;
            }
            int index1 = getIndex(r1, c1);
            int index2 = getIndex(r2, c2);
            if(size[index1] == 0 || size[index2] == 0) {
                return;
            }
            int node1 = find(index1);
            int node2 = find(index2);
            if (node1 != node2) {
                if (size[node1] >= size[node2]) {
                    parent[node2] = node1;
                    size[node1] += size[node2];
//                    size[node2] = 0;
                } else {
                    parent[node1] = node2;
                    size[node2] += size[node1];
//                    size[node1] = 0;
                }
                sets--;
            }
        }

        public int addLands(int r, int c) {
            int index = getIndex(r, c);
            if (size[index] == 0) {
                parent[index] = index;
                size[index] = 1;
                sets++;
                union(r, c, r - 1, c);
                union(r, c, r + 1, c);
                union(r, c, r, c - 1);
                union(r, c, r, c + 1);
            }
            return sets;
        }
    }

    public static void main(String[] args) {
        int[][] positions = {{0, 0}, {0, 1}, {1, 2}, {2, 1}};  // 1,1,2,3
        List<Integer> list = numIslands21(3, 3, positions);
        System.out.println(list.toString());
    }
}
